Information in optical networks is transmitted through optical fibers as optical signals. Each link may operate at a speed of the order of terabits per second, which is much faster than the currently available electronic devices for signal reception and transmission. Wavelength Division Multiplexing (WDM) technology allows more efficient use of the huge capacity of optical fibers by permitting the simultaneous transmission of different channels along the same fiber, with each channel using a different wavelength.
An all-optical point-to-point connection between two nodes is called a lightpath. It is characterized by its route and the wavelength in which it is multiplexed. Two lightpaths may use the same wavelength, provided they do not share any common fiber. Such networks require a large number of available wavelengths, especially when wavelength conversion is not available.
Given an optical network and a set of lightpath requests, the problem of Routing and Wavelength Assignment (RWA) in WDM optical networks consists in routing the set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned to different wavelengths. Variants of RWA are characterized by different optimization criteria and traffic patterns, as discussed in papers by J. S. Choi, N. Golmie, F. Lapeyrere, F. Mouveaux, and D. Su, A functional classification of routing and wavelength assignment schemes in DWDM networks: Static case, Proceedings of the 7th International Conference on Optical Communication and Networks, pages 1109-1115, Paris, 2000, and H. Zang, J. P. Jue, and B. Mukherjee, A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks, Optical Networks Magazine, 1:47-60, 2000.
In what is commonly referred to as “min-RWA,” all lightpath requests are known beforehand. No wavelength conversion is available, i.e. a lightpath must be assigned the same wavelength on all fibers in its route. The objective is to minimize the total number of wavelengths used in the network. This is also known to those skilled in the art as the Path Coloring Problem.
The current state-of-art heuristics for min-RWA were developed by Skorin-Kapov. See N. Skorin-Kapov, Routing and Wavelength Assignment in Optical Networks Using Bin Packing Based Algorithms, European Journal of Operational Research, 177: 1167-1179, 2007. Each wavelength is represented by a different copy of a bidirected graph G=(V, A) that represents the physical topology of an optical network. Vertices in V and arcs in A represent network nodes and fibers, respectively. Lightpaths arc-disjointly routed in the same copy of G are assigned the same wavelength. The copies of G are associated with the bins, and the lightpaths with the items of a bin packing problem. See, A. C. F. Alvim, C. C. Ribeiro, F. Glover, and D. J. Aloise, A hybrid improvement heuristic for the one-dimensional bin packing problem, Journal of Heuristics, 10:205-229, 2004. The min-RWA determination is reformulated as that of packing the lightpaths using a minimum number of bins.
The size of a lightpath is defined as the hop-count shortest path between its endnodes in G. Lightpaths are not necessarily routed on shortest paths of the original network. This is because whenever a lightpath is placed in a bin (i.e., a copy of G), all arcs in its route are deleted from the corresponding copy of G to avoid that other lightpaths use them. Therefore, the next lightpaths packed in that bin might not be able to be routed on a shortest path.
Four min-RWA heuristics have been developed based on classical bin packing heuristics: (i) FF-RWA, based on the First Fit heuristic, (ii) BF-RWA, based on the Best Fit heuristic, (iii) FFD-RWA, based on the First Fit Decreasing heuristic, and (iv) BFD-RWA, based on the Best Fit Decreasing heuristic.
The following is pseudo-code of bin packing heuristics for FF-RWA, BF-RWA, FFD-RWA, and BFD-RWA, all of which are quite similar:
begin heuristic(G, τ, d)1.   Let t be a permutation of the lightpaths in τ;2.   Set Ω ← ∅ and S ← ∅;3.   for i = 1:...:|t| do4.    Find the bin ω ∈ Ω where the shortest path of t1 in ω has lessthan d arcs;5.    if no such a bin exists then do7.     ω ← new copy of G;8.     Ω ← Ω 520  {ω};9.    end if10.   Let p1 be the shortest path between the endnodes of t1 in ω;11.   S ← S 520  (p1,ω);12. Delete edges in path p1 from ω;13. end-for;14. return S;end
The inputs are the graph G, the set τ of lightpath requests, and the value d of the maximum number of links in each route. As suggested by Skorin-Kapov, d is set to be the maximum of the square root of the number of links in the network and the diameter of G (i.e., the maximum value of a shortest path between any two nodes in the network). The output is a set S of tuples (pi,ωi), for i=1, . . . , |τ|, where pi is the route followed by lightpath ti and ωi is the wavelength with which it is multiplexed. With reference to the above pseudo-code, a permutation t of lightpaths in τ is built in line 1. In FF-RWA and BF-RWA, lightpaths are randomly distributed in t, while in FFD-RWA and BFD-RWA, they are sorted in non-increasing order of their sizes. In line 2, the set S and the set Ω of copies of G are initialized. The lightpaths are routed and assigned a wavelength in lines 3 to 13, one at a time, according to their order in t. A bin ωεΩ in which lightpath ti can be routed with less than d arcs is sought in line 4. FF-RWA and FFD-RWA stop at the first bin found, while BF-RWA and BFD-RWA scan all bins in Ω and select that in which ti fits with the smallest number of arcs (since the arcs in each copy of G are not necessarily the same). Let pi be the shortest path between the endnodes of ti in ω. If there is no bin in Ω where pi fits with less than d arcs, then ti is routed on a new copy of G that is created in line 7 and added to set Ω in line 8. The tuple (pi,ω) is added to the solution in line 11, and all arcs in pi are deleted from ω in line 12 to avoid that other lightpaths are routed on those arcs in this copy of G.
FIG. 1 is a flow-diagram of the process described above. In step 100, the procedure starts. At step 102, the following are input: graph G=[V, E], τ and d. Vertices V and edges E represent nodes and fibers, respectively, and d represents the diameter, i.e., the longest path between any two nodes in G. At step 104, no bins are open yet so the following are intialized: t←permutation of τ, bins Ω←Ø (empty set), Solution S←Ø (empty set). If i>|t| at 106, then the solution S is returned at block 108 and the procedure terminates at block 110. If the answer at step 106 is negative, then step 112 calculates the bin ω in Ω where the shortest path of ti can be routed with less than d arcs. If no such bin ω exists at step 114, then step 116 assigns a new copy of G to a bin ω and updates Ω. At step 118, the shortest path pi is computed between endpoints of ti in bin ω and the solution is updated S←S∪{pi,ωi}. At step 120, all arcs (edges) in pi are deleted from ω. Step 122 then increments i and the procedure loops back to step 106.
FIG. 2a depicts an exemplary 6-node network that forms an initial graph G. For this graph, τ={(1,6),(2,5),(3,4),(2,6)}, d=max{√{square root over (|E|)}, diameter(G)}, where |E|=8→√{square root over (8)}=2√{square root over (2)}. Accordingly, the diameter of G=5, which is the longest path between any of the two links, i.e., G=|{1→2→3→5→4→6}|=5. Let t={1, 2,3,4} be a permutation of P1, P2, P3, P4, therefore pairs are routed in this order: P1, P2, P3, P4. In accordance with the above, step 104 in FIG. 1 sets Ω=Ø (start with no bins) and S=Ø (start with no solution). For i=1, Pi=(1,6), a bin ω1 is created with graph G of FIG. 2a. The shortest path (1,6)=1→2→4→6 of size 3 (step 118, FIG. 1). Wavelength ω1 is then assigned to P1→S={(P1,ω1)}, and P1 is removed from bin ω1. This results in the updated graph G of FIG. 2b. For i=2, P2=(2,5) and the shortest path (2,5) in ω1=2→3→5 of size 2. Wavelength ω1 is then assigned to P2→S={(P1,ω1),(P2,ω1)}, and P2 is removed from ω1. The updated graph G is shown in FIG. 2c. For i=3, P2=(3,4) there is no path of length d or less in ω1, thus to go between nodes 3 and 4, a new bin has to be created ω2 (FIG. 2d). The shortest path (3,4) in ω2=3→2→4 of size 2. Wavelength ω2 is assigned to P3 and added to the solution P3→S={(P1,ω1), (P2,ω1), (P3,ω2)}. The links in path P3 are then removed from ω2 and the updated graph appears in FIG. 2e. For i=4, P4=(2,6), the shortest path in ω2 is ω2=2→1→3→5→6 of size 4. Wavelength ω2 is assigned to P4 and added to the solution P4→S={(P1,ω1),(P2,ω1),(P3,ω2),(P4,ω2)}. For i>4 the process stops (step 106, FIG. 1) and the solution S for this case uses 2 wavelengths (min-RWA).
While the above-described example is very simple, the running times reported by Skorin-Kapov for typical networking min-RWA determinations using these heuristics were very high. On the largest instances, running times of up to 8 minutes on a Pentium IV 2.8 GHz have reported. Let n=|V|, m=|A|, and l=|τ|. Furthermore, let csp (m,n) be the computational complexity of a one-to-all shortest path algorithm applied to G, and Cdel (m,n) be the complexity of deleting an arc from G. The worst case complexity T(n,m,l) of FF-RWA, BF-RWA, FFD-RWA, and BFD-RWA is calculated as follows. For the sake of simplicity, it will be assumed that n<l, which holds for all real and artificial networks in the literature. With reference to the above pseudo-code, first, all-to-all shortest paths are calculated in time O(n·csp (m,n)) in line 1, and sets Ω and S are initialized in constant time in line 2. Next, lines 3 to 13 are repeated for each lightpath ti, with i=1, . . . ,l. In line 4, a bin where ti fits with less than d arcs is found in time O(l·csp (m,n)). A new copy of G is created in time O(m) in line 7 and added to set Ω in constant time in line 8. Finally, the set S is updated in constant time in line 11, while the arcs in pi are deleted from ω in time O(d·cdel) in line 12. Therefore, the worst case complexity of these heuristics is:
                              T          ⁡                      (                          n              ,              m              ,              l                        )                          =                ⁢                              O            ⁡                          (                              n                ·                                                      c                    sp                                    ⁡                                      (                                          m                      ,                      n                                        )                                                              )                                +                      O            ⁡                          (              1              )                                +                                                ⁢                  O          ⁡                      (                          l              ·                              (                                                      l                    ·                                                                  c                        sp                                            ⁡                                              (                                                  m                          ,                          n                                                )                                                                              +                  m                  +                  1                  +                                      d                    ·                                                                  c                        del                                            ⁡                                              (                                                  m                          ,                          n                                                )                                                                                            )                                      )                                                  =                ⁢                              O            ⁡                          (                                                n                  ·                                                            c                      sp                                        ⁡                                          (                                              m                        ,                        n                                            )                                                                      +                                                      l                    2                                    ·                                                            c                      sp                                        ⁡                                          (                                              m                        ,                        n                                            )                                                                      +                                  l                  ·                  m                                +                                  l                  ·                  d                  ·                                                            c                      del                                        ⁡                                          (                                              m                        ,                        n                                            )                                                                                  )                                .                    
The efficiency of the heuristics therefore depends on how fast a shortest path (SP) query is performed and how fast an arc is removed from G. The traditional implementations using Dijkstra's algorithm and single linked lists to represent the adjacency matrix of G lead to csp(m,n)=O(n·log n+m) and cdel(m,n)=O(n). Therefore, T(n,m,l)=O(n·(n·log n+m)+l2·(n·log n+m)+l·m+l·d·n)=O(l2·(n·log n+m)).
The inventors have discovered that it is possible to greatly improve the processing time of known min-RWA heuristics through the use of novel SP queries and arc removal.